package 力扣91;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @ClassName : Day10_160_相交链表_栈解法
 * @Author : 骆发茂
 * @Date: 2021/12/22 21:36
 * @Description : *这里要注意是节点相同，地址和值都要相同。
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/gong-shui-san-xie-zhao-liang-tiao-lian-b-h3bd/
 */
public class Day10_160_相交链表_栈解法 {
    public class Solution {
        public ListNode getIntersectionNode(ListNode a, ListNode b) {
            Deque<ListNode> d1 = new ArrayDeque(), d2 = new ArrayDeque();
            while (a != null) {
                d1.addLast(a);
                a = a.next;
            }
            while (b != null) {
                d2.addLast(b);
                b = b.next;
            }
            ListNode ans = null;
            while (!d1.isEmpty() && !d2.isEmpty() && d1.peekLast().equals(d2.peekLast())) {
                ListNode c1 = d1.pollLast(), c2 = d2.pollLast();//取队尾元素并删除
                // E removeLast() / E pollLast()
                ans = c1;
            }
            return ans;
        }
    }
}